home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Reference Guide / C-C++ Interactive Reference Guide.iso / c_ref / csource4 / 246_01 / cycle23.c < prev    next >
Text File  |  1987-10-29  |  5KB  |  233 lines
  1.  
  2.  
  3.  
  4. /* CYCLE23.C                     */
  5. /* program to analyze the cycles of a cellular   */
  6. /* automaton and report all the periodic states. */
  7. /* [Harold V. McIntosh, 21 May 1987]         */
  8.  
  9. # include <stdio.h>
  10.  
  11. # define KK     2            /* number of states/cell    */
  12. # define NS      8            /* number of distinct sums    */
  13. # define NW    24            /* pause after so many lines    */
  14.  
  15. int  arr1[16], arr2[16];
  16. unsigned int arry[16384];
  17. int  binrule[KK][KK][KK][KK][KK][KK][KK], rule[NS];
  18. int  cy, cp, mc, nc, nl;
  19.  
  20. main() {
  21. int  i;
  22.  
  23. printf("Rule number:\n\n");
  24. printf("0......1\n");
  25. for (i=0; i<NS; i++) rule[i]=kbdin()-'0';
  26. printf("\n");
  27.  
  28. totobin();
  29.  
  30. nc=0;
  31. nl=0;
  32.  
  33. printf("Cycles of length 5"); kwait(0);
  34.  mc=6;
  35.  cy=5;
  36.  cp=32;
  37.  pass1();
  38.  pass2();
  39.  pass4();
  40.  
  41. printf("Cycles of length 6"); kwait(0);
  42.  mc=5;
  43.  cy=6;
  44.  cp=64;
  45.  pass1();
  46.  pass2();
  47.  pass4();
  48.  
  49. printf("Cycles of length 7"); kwait(0);
  50.  mc=4;
  51.  cy=7;
  52.  cp=128;
  53.  pass1();
  54.  pass2();
  55.  pass4();
  56.  
  57. printf("Cycles of length 8"); kwait(0);
  58.  mc=4;
  59.  cy=8;
  60.  cp=256;
  61.  pass1();
  62.  pass2();
  63.  pass4();
  64.  
  65. printf("Cycles of length 9"); kwait(0);
  66.  mc=3;
  67.  cy=9;
  68.  cp=512;
  69.  pass1();
  70.  pass2();
  71.  pass4();
  72.  
  73. printf("Cycles of length 10"); kwait(0);
  74.  mc=3;
  75.  cy=10;
  76.  cp=1024;
  77.  pass1();
  78.  pass2();
  79.  pass4();
  80.  
  81. printf("Cycles of length 11"); kwait(0);
  82.  mc=3;
  83.  cy=11;
  84.  cp=2048;
  85.  pass1();
  86.  pass2();
  87.  pass4();
  88.  
  89. printf("Cycles of length 12"); kwait(0);
  90.  mc=2;
  91.  cy=12;
  92.  cp=4096;
  93.  pass1();
  94.  pass2();
  95.  pass4();
  96.  
  97. printf("Cycles of length 13"); kwait(0);
  98.  mc=2;
  99.  cy=13;
  100.  cp=8192;
  101.  pass1();
  102.  pass2();
  103.  pass4();
  104.  
  105. printf("Cycles of length 14"); kwait(0);
  106.  mc=2;
  107.  cy=14;
  108.  cp=16384;
  109.  pass1();
  110.  pass2();
  111.  pass4();
  112.  
  113. } /* end main */
  114.  
  115. /* Pass 1 makes arry[i] equal to the successor of i */
  116.  
  117. pass1() {int i, j, x;
  118.   printf(" Pass1\015");
  119.   for (j=0; j<cp; j++) {
  120.     x=j; for (i=0; i<cy; i++) {arr1[cy-i-1]=x%KK; x/=KK;};
  121.     evolve(cy);
  122.     x=0; for (i=0; i<cy; i++) x=KK*x+arr2[i]; arry[j]=x;
  123.   }; }
  124.  
  125. /* calculate one generation of evolution in a ring of length n */
  126.  
  127. evolve(n) int n; {
  128. int i;
  129.   arr2[0]=binrule[arr1[n-3]][arr1[n-2]][arr1[n-1]][arr1[0]][arr1[1]][arr1[2]][arr1[3]];
  130.   arr2[1]=binrule[arr1[n-2]][arr1[n-1]][arr1[0]][arr1[1]][arr1[2]][arr1[3]][arr1[4]];
  131.   arr2[2]=binrule[arr1[n-1]][arr1[0]][arr1[1]][arr1[2]][arr1[3]][arr1[4]][arr1[5]];
  132.   for (i=3; i<n-3; i++) arr2[i]=binrule[arr1[i-3]][arr1[i-2]][arr1[i-1]][arr1[i]][arr1[i+1]][arr1[i+2]][arr1[i+3]];
  133.   arr2[n-3]=binrule[arr1[n-6]][arr1[n-5]][arr1[n-4]][arr1[n-3]][arr1[n-2]][arr1[n-1]][arr1[0]];
  134.   arr2[n-2]=binrule[arr1[n-5]][arr1[n-4]][arr1[n-3]][arr1[n-2]][arr1[n-1]][arr1[0]][arr1[1]];
  135.   arr2[n-1]=binrule[arr1[n-4]][arr1[n-3]][arr1[n-2]][arr1[n-1]][arr1[0]][arr1[1]][arr1[2]];
  136. }
  137.  
  138. /* Pass 2 flags all links with an incoming arrow */
  139.  
  140. pass2() {int j, m, x;
  141. printf(" Pass2\015");
  142. do {
  143. m=0;
  144. for (j=0; j<cp; j++) arry[j]|=0x8000;
  145. for (j=0; j<cp; j++) {x=arry[j];
  146.  if (x!=0xFFFF) arry[x&0x7FFF]&=0x7FFF;};
  147. for (j=0; j<cp; j++) {
  148.  if ((arry[j]>0x7FFF) && (arry[j]!=0xFFFF)) {arry[j]=0xFFFF; m=1;};};
  149.  } while (m!=0);
  150. }
  151.  
  152. /* pass4 - print loops which remain */
  153.  
  154. pass4() {
  155. int j, x, y, m;
  156. printf(" pass4 \015");
  157. for (j=0; j<cp; j++) {
  158.  x=j; y=arry[j]; arry[j]=0xFFFF; m=0;
  159.  while (y!=0xFFFF) {prf(x,y); x=y; y=arry[x]; arry[x]=0xFFFF; m=1;};
  160.  if (m==1) kwait(0);
  161.  };
  162. }
  163.  
  164. /* change totalistic rule to general rule */
  165.  
  166. totobin() {
  167. int i0, i1, i2, i3, i4, i5, i6;
  168. for (i0=0; i0<KK; i0++) {
  169. for (i1=0; i1<KK; i1++) {
  170. for (i2=0; i2<KK; i2++) {
  171. for (i3=0; i3<KK; i3++) {
  172. for (i4=0; i4<KK; i4++) {
  173. for (i5=0; i5<KK; i5++) {
  174. for (i6=0; i6<KK; i6++) {
  175. binrule[i0][i1][i2][i3][i4][i5][i6]=rule[i0+i1+i2+i3+i4+i5+i6];
  176. };};};};};};};
  177. }
  178.  
  179. /* print the link */
  180.  
  181. prf(j,x) int j, x; {int i, y;
  182.   kwait(1);
  183.   y=j; for (i=0; i<cy; i++) {arr1[i]=y%KK; y/=KK;};
  184.   for (i=0; i<cy; i++) printf("%1d",arr1[i]);
  185.   printf("-");
  186.   y=x; for (i=0; i<cy; i++) {arr1[i]=y%KK; y/=KK;};
  187.   for (i=0; i<cy; i++) printf("%1d",arr1[i]);
  188.   printf("  ");
  189. }
  190.  
  191. /* print arry - for diagnostic purposes */
  192. pall() {int j;
  193. for (j=0; j<cp; j++) printf("%4d",arry[j]);
  194. }
  195.  
  196. /* print cycle - for diagnostic purposes */
  197. pcy() {int j;
  198. for (j=0; j<cy; j++) printf("%1d",arr2[j]);
  199. }
  200.  
  201. /* limit j to interval (i,k) */
  202. int lim(i,j,k) int i, j, k;
  203.     {if (i>=j) return i; if (k<=j) return k; return j;}
  204.  
  205. /* keyboard status */
  206. kbdst() {return bdos(11)&0xFF;}
  207.  
  208. /* direct keyboard input, no echo */
  209. kbdin() {int c;
  210. if ((c=bdos(7)&0xFF)=='\0') c=(bdos(7)&0xFF)|0x80;
  211. videoputc(c,1);
  212. return c;}
  213.  
  214. /* pause at the end of a full screen */
  215. /* kwait(0) - <cr><lf> and count it  */
  216. /* kwait(1) - count columns          */
  217.  
  218. kwait(i) int i; {
  219. switch (i) {
  220.   case 0: printf("\n"); nc=0; nl++; break;
  221.   case 1: if (nc==mc) {printf("&\n"); nc=1; nl++;} else nc++; break;
  222.   default: break;};
  223. if (nl==NW) {
  224.   nl=0;
  225.   printf(" press any key to continue\015");
  226.   while (kbdst()) {};
  227.   kbdin();
  228.   printf("-                         \n");
  229.   };
  230. }
  231.  
  232. /* end */
  233.